# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        """TLE
        """

        def dfs(root, head, length, ans):
            if ans[0]:
                return []
            if root is None:
                return []
            leftPaths = dfs(root.left, head, length, ans)
            rightPaths = dfs(root.right, head, length, ans)
            paths = []
            if len(leftPaths) == 0 and len(rightPaths) == 0:
                paths = [[root.val]]
            else:
                for path in leftPaths:
                    newPath = [root.val] + path
                    paths.append(newPath[:length])
                for path in rightPaths:
                    newPath = [root.val] + path
                    paths.append(newPath[:length])
            for path in paths:
                if len(path) < length:
                    continue
                node = head
                i = 0
                res = True
                while node:
                    if node.val != path[i]:
                        res = False
                        break
                    node = node.next
                    i += 1
                if res:
                    ans[0] = True

            return paths

        length = 0
        node = head
        while node:
            length += 1
            node = node.next
        ans = [False]
        dfs(root, head, length, ans)
        return ans[0]
